package com.gwcloud.leetcode.offers;

/** 
* @ClassName   : Leetcode0190 
* @author      : ganwei 
* @date        : 2020年6月1日 
* @Description : TODO 
*/
public class Leetcode0190 {
	/**
	 * -正则表达式匹配，解题思路为回溯算法
	 */
    public boolean isMatch(String s, String p) {

    	return backtrace(s,p);
    }
    /**
     * -回溯主体
     */
    public boolean backtrace(String s, String p) {
    	/**
    	 * 回溯出口ss
    	 */
		if(p.isEmpty()){
    		return s.isEmpty();
    	}
		
    	//回溯路径选择
    	boolean firstmatch = (!s.isEmpty() &&
    			( p.charAt(0) == s.charAt(0) || p.charAt(0) == '.'));
    	
    	if(p.length() >= 2 && p.charAt(1)=='*'){
    		return isMatch(s,p.substring(2)) || (firstmatch && isMatch(s.substring(1),p));
    	}else{
    		return firstmatch&&isMatch(s.substring(1),p.substring(1));
    	}
    }
    
    /**
     * -主函数
     */
    public static void main(String[] args) {
    	Leetcode0190 l0190 = new Leetcode0190();
    	//System.out.println(l0190.isMatch("aab", "c*a*b"));
    	System.out.println("a*".substring(2));
    }
}
